Codeforces/Codeforces Beta Round #90/D/d.2.cpp

   1 // Andrés Mejía
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 const int MAXN = 1000005;
  34
  35 int p[2 * MAXN];
  36 int z[2 * MAXN];
  37
  38 int main(){
  39     string a, b;
  40     while (getline(cin, a) and getline(cin, b)) {
  41         int n = a.size();
  42         if (n != b.size()) {
  43             puts("-1 -1");
  44             continue;
  45         }
  46
  47         string s1 = a; reverse(s1.begin(), s1.end()); s1 += '\n' + b;
  48         string s2 = b + '\n' + a;
  49
  50         // { s1 == a^r$b }
  51         // { s2 == b$a }
  52
  53         // Find prefix function of a^r$b
  54         p[0] = 0;
  55         for (int i = 1; i < 2 * n + 1; ++i) {
  56             int k = p[i - 1];
  57             while (k > 0 and s1[i] != s1[k]) k = p[k - 1];
  58             if (s1[i] == s1[k]) k++;
  59             p[i] = k;
  60         }
  61
  62         // Find z function of b$a
  63         z[0] = 0;
  64         for (int i = 1, l = 0, r = 0; i < 2 * n + 1; ++i) {
  65             z[i] = 0;
  66             if (i <= r) z[i] = min(z[i - l], r - i + 1);
  67             while (i + z[i] < 2 * n + 1 && s2[z[i]] == s2[i + z[i]]) ++z[i];
  68             if (i + z[i] - 1 > r) {
  69                 l = i;
  70                 r = i + z[i] - 1;
  71             }
  72         }
  73
  74         int ans_i = -1, ans_j = -1;
  75         for (int i = 0; i < n; ++i) {
  76             if (a[i] != b[n - i - 1]) break;
  77             int len = p[2 * n - 1 - i]; // Length of s[j, n-1]^r
  78             if (len == 0) continue;
  79             if (z[n + 1 + i + 1] >= n - len - i - 1) {
  80                 ans_i = i, ans_j = n - len;
  81             }
  82         }
  83         printf("%d %d\n", ans_i, ans_j);
  84     }
  85     return 0;
  86 }